package automata.conversion;

/*
 * Convierte un AFN a un AFD. Maneja la conversión del automata finito no determinista
 * al automata finito determinista por medio del algoritmo de subconjuntos.
 * 
 * @autor Francisco Javier Ponce Cruz
 * @version v1 (Ago 2013)
 * */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import automata.modelo.Automata;
import automata.modelo.Transicion;

public class ConversionAF {

	private Automata afn;
	private Automata afd;
	public static int maxCiclos = 15;

	public ConversionAF(Automata afn) {
		this.afn = afn;
		afd = new Automata();
	}

	/**
	 * Calcula las transiciones Epsilon, a partir del estado que recibe por
	 * argumento. Observaciones: Si el estado no esta en el conjunto de estados
	 * del automata, se termina el programa.
	 * 
	 * @param String
	 *            'estado' contenido en los estados del AF.
	 * @return HashSet<String> estados de transición Epsilon.
	 */
	private HashSet<String> cerraduraEpsilon(String estado) {
		ArrayList<String> acumulador = new ArrayList<String>();
		ArrayList<Transicion> listaTransiciones = afn.getTransiciones();
		acumulador.add(estado);
		String estadoActual;
		int i = 0;

		while (true) {
			try {
				estadoActual = acumulador.get(i);
				for (Transicion t : listaTransiciones) {
					String desde = Integer.toString(t.getDesde());
					if (desde.equals(estadoActual)) {
						if (t.getSimbolo() == Automata.SIMBOLO_VACIO) {
							if (!acumulador.contains(Integer.toString(t
									.getHasta())))
								acumulador.add(Integer.toString(t.getHasta()));
						}
					}
				}
				i++;
			} catch (IndexOutOfBoundsException e) {
				break;
			}
		}
		HashSet<String> acumuHash = new HashSet<>(acumulador);
		return acumuHash;
	}

	/**
	 * Verifica la transición con respecto al simbolo, a partir del estado que
	 * recibe por argumento. Observaciones: Si el estado no esta en el conjuntos
	 * de estados del automata, se termina el programa.
	 * 
	 * @param String
	 *            Estado de partida
	 * @param Character
	 *            'simbolo' de transcicion
	 * @return una lista con los estados de transición al simbolo. Puede ser
	 *         null
	 */
	private HashSet<String> mover(String estado, Character simbolo) {
		HashSet<String> acumulador = new HashSet<String>();
		ArrayList<Transicion> listaTransiciones = afn.getTransiciones();
		for (Transicion t : listaTransiciones) {
			String desde = Integer.toString(t.getDesde());
			if (desde.equals(estado)) {
				if (t.getSimbolo() == simbolo)
					acumulador.add(Integer.toString(t.getHasta()));
			}
		}
		return acumulador;
	}

	/**
	 * Descripcion: cordina la busqueda de transiciones hacia un simbolo a
	 * partir del conjunto que recibe por argumento. Recibe: una lista y un
	 * string 'conjunto' y 'simbolo' contenidos en los estados y entradas del AF
	 * respectivamente. Devuelve: una lista con los estados de transición al
	 * simbolo. Observaciones: Si el estado no esta en el conjuntos de estados
	 * del automata, se termina el programa (Lo verifican carraduraEpsilon y
	 * mover).
	 */
	private HashSet<String> irA(HashSet<String> conjunto, Character simbolo) {
		HashSet<String> acumuladorMov = new HashSet<String>();
		HashSet<String> acumuladorCe = new HashSet<String>();

		for (String edo : conjunto) {
			acumuladorMov = mover(edo, simbolo);
			for (String e : acumuladorMov)
				acumuladorCe.addAll(cerraduraEpsilon(e));
		}

		return acumuladorCe;
	}

	/**
	 * Realiza la conversión de AFN a AFD. Observaciones: Muestra los conjuntos
	 * correspondientes a cada estado del AFD.
	 * 
	 * @return Automata
	 */

	public Automata convertir() {
		ArrayList<HashSet<String>> conjuntos = new ArrayList<HashSet<String>>();
		ArrayList<String> nombres = new ArrayList<String>();
		HashSet<String> estado, conjuntoIra;
		int nombreEstados = 0, indexEstados = 0;

		estado = cerraduraEpsilon(afn.getEstadoInicial());
		afd.setEstadoInicial(Integer.toString(nombreEstados));
		afd.addEstado(afd.getEstadoInicial());// Agregamos el estado inicial a
												// los estados AFD.
		conjuntos.add(indexEstados, estado);
		System.out.println(conjuntos);
		nombres.add(indexEstados, Integer.toString(nombreEstados));
		indexEstados++;
		nombreEstados++;
		int conjunto = conjuntos.size(), aux;// inicializa numero de estados en
		HashSet<String> estadoActual;// el automata

		aux = conjunto;
		int i = 0;
		while (true) {
			try {
				estadoActual = conjuntos.get(i);
				/** Iteramos cada simbolo con el estado actual */
				for (Character entrada : afn.getSimbolos()) {
					if (entrada == '@') {
						continue;
					}
					conjuntoIra = irA(estadoActual, entrada);

					if (conjuntos.contains(conjuntoIra)) {
						afd.addTransicion(
								nombres.get(conjuntos.indexOf(estadoActual)),
								entrada,
								nombres.get(conjuntos.indexOf(conjuntoIra)));
					} else {
						conjuntos.add(indexEstados, conjuntoIra);
						nombres.add(indexEstados,Integer.toString(nombreEstados));
						indexEstados++;
						nombreEstados++;
						afd.addTransicion(
								nombres.get(conjuntos.indexOf(estadoActual)),
								entrada,
								nombres.get(conjuntos.indexOf(conjuntoIra)));
						afd.addEstado(nombres.get(conjuntos.indexOf(conjuntoIra)));
					}
					afd.addSimbolo(entrada);
				}
				i++;
			} catch (IndexOutOfBoundsException e) {
				System.out.println("Mensaje" + e.getMessage());
				break;
			}
			
			for (String edo : afn.getEstadosFinales())
				for (HashSet<String> conj : conjuntos)
					if (conj.contains(edo))
						afd.addEstadoFinal(nombres.get(conjuntos.indexOf(conj)));
		}
		return afd;
	}
}